package com.techyuan.algorithm.structure.map;

import java.util.*;

/**
 * @author tianjuntao
 */
@SuppressWarnings("unchecked")
public class OpenAddressMap<V> implements Map<Integer, V> {
    private Integer[] keyData;
    private Object[] valueData;
    private int size;
    private int mod = 11;
    private static Integer nil = Integer.MIN_VALUE;

    public OpenAddressMap(int capacity) {
        keyData = new Integer[capacity];
        valueData = new Object[capacity];
        mod = capacity;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean containsKey(Object key) {
        Integer intKey = (Integer) key;
        int i = 0;
        while (i < mod) {
            int hash = MapUtils.QuadraticProbing(intKey, mod, i);
            if ((keyData[hash] != null || !keyData[hash].equals(nil)) && keyData[hash].equals(intKey)) {
                return true;
            } else if (keyData[hash] == null)
                break;
            else
                i = i + 1;
        }
        return false;
    }

    public boolean containsValue(Object value) {
        if (value == null)
            return false;

        for (Object v : valueData) {
            if (v != null && value.equals(v))
                return true;
        }
        return false;
    }

    public V get(Object key) {
        Integer intKey = (Integer) key;
        int i = 0;
        while (i < mod) {
            int hash = MapUtils.QuadraticProbing(intKey, mod, i);
            if ((keyData[hash] != null || keyData[hash] != nil) && keyData[hash].equals(intKey)) {
                return (V) valueData[hash];
            } else if (keyData[hash] == null)
                break;
            else
                i = i + 1;
        }
        return null;
    }

    public V put(Integer intKey, V value) {
        int i = 0;
        while (i < mod) {
            int hash = MapUtils.QuadraticProbing(intKey, mod, i);
            if (keyData[hash] == null || keyData[hash].equals(nil)) {
                keyData[hash] = intKey;
                valueData[hash] = value;
                size++;
                return value;
            } else
                i = i + 1;
        }
        return null;
    }

    public V remove(Object key) {
        Integer intKey = (Integer) key;
        int i = 0;
        while (i < mod) {
            int hash = MapUtils.QuadraticProbing(intKey, mod, i);
            if ((keyData[hash] != null || keyData[hash].equals(nil)) && keyData[hash].equals(intKey)) {
                keyData[hash] = nil;
                V value = (V) valueData[hash];
                valueData[hash] = null;
                size--;
                return value;
            } else if (keyData[hash] == null)
                break;
            else
                i = i + 1;
        }
        return null;
    }

    public void putAll(Map<? extends Integer, ? extends V> m) {
        for (Map.Entry<? extends Integer, ? extends V> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    public void clear() {
        size = 0;
        for (int i = 0; i < keyData.length; i++)
            keyData[i] = null;
        for (int i = 0; i < valueData.length; i++)
            valueData[i] = null;
    }

    public Set<Integer> keySet() {
        HashSet<Integer> keys = new HashSet<Integer>();
        for (int i = 0; i < keyData.length; i++) {
            if (keyData[i] != null && keyData[i] != nil)
                keys.add(i);
        }
        return keys;
    }

    public Collection<V> values() {
        ArrayList<V> values = new ArrayList<V>();
        for (int i = 0; i < valueData.length; i++) {
            if (valueData[i] != null)
                values.add((V) valueData[i]);
        }
        return values;
    }

    public Set<Entry<Integer, V>> entrySet() {
        HashSet<Entry<Integer, V>> entrySet = new HashSet<Entry<Integer, V>>();
        for (int i = 0; i < keyData.length; i++) {
            if (keyData[i] != null && keyData[i] != nil)
                entrySet.add(new AbstractMap.SimpleEntry<Integer, V>(keyData[i], (V) valueData[i]));
        }
        return entrySet;
    }

    public static void main(String[] args) {
        Map<Integer, String> map = new OpenAddressMap<String>(256);
        for (int i = 0; i < 256; i++) {
            map.put(i, "数字：" + i);
        }
    }
}
